import java.util.*;

public class Main {
    public static List<String> topKFrequent(String[] words, int k) {
        //1、统计单词出现的次数  key:单词   val: 次数
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (map.get(word) == null) {
                map.put(word, 1);
            } else {
                int val = map.get(word);
                map.put(word, val + 1);
            }
        }
        //2、建立大小为k的 小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap =
                new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        //比较频率
                        if (o1.getValue().compareTo(o2.getValue()) == 0) {
                            //做一个转换
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        //return o1.getValue()-o2.getValue();
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });

        //遍历map
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                //此时需要和堆顶元素去比较
                Map.Entry<String, Integer> top = minHeap.peek();
                Integer val = top.getValue();
                // entry是当前的元素
                if (val.compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if (val.compareTo(entry.getValue()) == 0) {
                    String key = top.getKey();
                    if (key.compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String key = minHeap.poll().getKey();
            list.add(key);
        }
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.get("123");
    }

    public List<String> topKFrequent1(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();

        //统计单词出现的次数
        for (String str : words) {
            if (map.get(str) == null) {
                map.put(str, 1);
            } else {
                int val = map.get(str);
                map.put(str, val + 1);
            }
        }

        //topK问题返回前k个最大值 所以建立小根堆
        PriorityQueue<Map.Entry<String, Integer>> que = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {

                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }

                return o1.getValue().compareTo(o2.getValue());
            }
        });
            //先放入K个元素 放完比较 最后最小的值都比其他值大了说明优先级队列里面已经是最大的K个值了
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if(que.size() < k) {
                que.offer(entry);
            }else {
                Map.Entry<String, Integer> top = que.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    que.poll();
                    que.offer(entry);
                    //频率相等时按照字典顺序排序  字典顺序就是a-z  从小打大
                }else if(top.getValue().compareTo(entry.getValue()) == 0) {
                    String str = top.getKey();
                    if(str.compareTo(entry.getKey()) > 0) {
                        que.poll();
                        que.offer(entry);
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for(int i = 0; i < k;i++) {
            String str= que.poll().getKey();
            list.add(str);
        }

        Collections.reverse(list);

        return list;
    }
}

